洛谷 P14507 · 难度 普及+/提高

题目描述

给定一个正整数 $n$ 和 $n$ 个二元组 $(a_i,b_i)$，表示现在有 $b_i$ 个大小为 $a_i$ 的数。

定义一个可重集合的 $\mathrm{mex}$ 为最小的没有在这个集合中出现的自然数。

你需要将这 $\sum _{i=1}^n{b}_i$ 个数划分成 $k(k\ge 1)$ 个可重集合，使得这 $k$ 个可重集合的 $\mathrm{mex}$ 之和恰好为 $m$，并最小化这个 $k$。

现在有 $q$ 组询问，对于每一组询问给定一个 $m$，你需要输出最小的 $k$，如果无解则输出 $-1$。

输入格式

本题包含多组测试数据。

输入的第一行包含一个整数 $T$，表示测试数据的组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

• 第一行包含两个整数 $n,q$，表示有 $n$ 个二元组并且存在 $q$ 次询问。

• 对于接下来的 $n$ 行每行输入两个整数，表示二元组 $(a_i,b_i)$。

• 对于接下来的 $q$ 行每行输入一个整数 $m$ 表示一次询问。

输出格式

对于每组测试数据输出 $q$ 行，每行包含一个整数，表示对应的答案。

说明/提示

【样例 1 解释】

对于 $m=0$ 和 $m=8$ 都可以证明不存在划分方案使得有解。

对于 $m=3$，可以将所有数划分为一个集合 $S=\{0,0,0,1,1,1,1,2,4\}$，这个集合的 $\mathrm{mex}$ 为 $3$。

对于 $m=4$，可以将所有数划分为两个集合 $S_1=\{0,0,1,1,1,1,2\}$ 和 $S_2=\{0,4\}$，这两个集合的 $\mathrm{mex}$ 之和为 $3+1=4$。

对于 $m=7$，可以将所有数划分为三个集合 $S_1=\{0,1,2,4\},S_2=\{0,1\},S_3=\{0,1,1\}$，这三个集合的 $\mathrm{mex}$ 之和为 $3+2+2=7$。

【样例 2 解释】

我们提供了一组大样例，该样例共有 $10$ 组测试数据，其中第 $i(1\le i\le 10)$ 组测试数据满足数据范围中描述的测试点 $2i-1$的限制。

数据范围

对于所有的数据,满足:

• $1\le T\le 10$。
• $1\le n,q\le {10}^5,0\le a_i\le {10}^9,a_{i-1}<a_i,1\le b_i\le {10}^9,0\le m\le {10}^{18}$。

::cute-table

测试点编号	$n,q\le$	$m\le$	特殊性质
$1\sim 2$	$10$	$10$	AB
$3\sim 4$	$1000$	$1000$	B
$5\sim 8$	$1000$	${10}^4$	无
$9\sim 12$	${10}^5$	${10}^{18}$	C
$13\sim 14$	${10}^5$	${10}^{18}$	D
$15\sim 20$	${10}^5$	${10}^{18}$	无

• 特殊性质 A：保证所有 $b_i$ 均为 $1$。

• 特殊性质 B：保证所有 $b_i$ 均相等。

• 特殊性质 C：保证 $b_i$ 单调不增。

• 特殊性质 D：保证 $a_i$ 在数据范围内均匀随机生成。

本题输入数据较大，请选手自行选择较快的输入方式。

样例

样例 1

输入

1
4 5
0 3
1 4
2 1
4 1
0
3
4
7
8

输出

-1
1
2
3
-1